﻿using System.Text;

namespace DataStructure;

//三元组顺序表矩阵类
public class TSMatrix<E> : ITMatrix<E> where E : struct
{
    private class Triple //三元组类型
    {
        public int r; //行号
        public int c; //列号 
        public E e;   //元素值        
    }

    private SeqList<Triple> tripleSeqList; //三元组顺序表

    public int Rows { get; } //稀疏矩阵的行数
    public int Cols { get; } //稀疏矩阵的列数
    public int Nums { get; set; } //顺序表三元组个数

    public TSMatrix(int Rows, int Cols, int Nums)
    {
        this.Rows = Rows;
        this.Cols = Cols;
        this.Nums = Nums; //三元组（非0元）个数
        tripleSeqList = new SeqList<Triple>();
    }

    public TSMatrix(E[,] sparseMatrix)
    {
        Rows = sparseMatrix.GetLength(0);
        Cols = sparseMatrix.GetLength(1);
        Nums = 0;

        tripleSeqList = new SeqList<Triple>();

        //按行序方式扫描所有元素
        for (int i = 0; i < Rows; i++)
        {
            for (int j = 0; j < Cols; j++)
            {
                if (!sparseMatrix[i, j].Equals(default(E))) //只存储非零元素
                {
                    Triple triple = new Triple
                    {
                        r = i,
                        c = j,
                        e = sparseMatrix[i, j]
                    };

                    tripleSeqList.AddLast(triple);
                    Nums++;
                }
            }
        }
    }

    public TSMatrix(string file)
    {
        StreamReader sr = new StreamReader(file);

        string line = sr.ReadLine();
        string[] str = line.Split(' ');

        Rows = int.Parse(str[0]);
        Cols = int.Parse(str[1]);
        Nums = int.Parse(str[2]);

        tripleSeqList = new SeqList<Triple>();
        for (int i = 0; i < Nums; i++)
        {
            line = sr.ReadLine();
            str = line.Split(' ');

            Triple triple = new Triple
            {
                r = int.Parse(str[0]),
                c = int.Parse(str[1]),
                e = (E)Convert.ChangeType(str[2], typeof(E))
            };

            tripleSeqList.AddLast(triple);
        }

        sr.Close();
    }

    public E[,] SparseMatrix()
    {
        E[,] sparseMatrix = new E[Rows, Cols];

        for (int k = 0; k < Nums; k++)
        {
            sparseMatrix[tripleSeqList[k].r, tripleSeqList[k].c] = tripleSeqList[k].e;
        }

        return sparseMatrix;
    }

    private bool GetByCoord(int i, int j, out Triple triple)
    {
        triple = null;

        if (i < 0 || i >= Rows || j < 0 || j >= Cols)
        {
            return false; //索引越界，操作失败，返回false。
        }

        //查三元组表中(不为零)的第i行第j列元素
        int k = 0;
        while (k < Nums && tripleSeqList[k].r < i) //先找所在行i
        {
            k++;
        }
        while (k < Nums && tripleSeqList[k].r == i && tripleSeqList[k].c < j) //在第i行中再找所在列j
        {
            k++;
        }

        if (k < Nums && tripleSeqList[k].r == i && tripleSeqList[k].c == j) //表中存在此元素
        {
            triple = tripleSeqList[k]; //提取表中不为零的此元素值，替换前面给指定变量所赋的零值。
        }

        return true;    //操作成功，返回真。   
    }

    public bool Assign(int i, int j, out E assignedE)
    {
        assignedE = default;

        bool res = GetByCoord(i, j, out Triple triple);
        if (!res)
        {
            return false;
        }

        if (triple is not null)
        {
            assignedE = triple.e;
        }

        return true;
    }

    public bool Amend(int i, int j, E newE)
    {
        bool res = GetByCoord(i, j, out Triple triple);
        if (!res)
        {
            return false;
        }

        if (triple is not null) //表中存在此元素
        {
            if (newE.Equals(default(E)))    //如果给该元素赋值为0
            {
                tripleSeqList.Remove(triple); //将该元素从表中删除。
                Nums--;                    //表元素个数减一
            }
            else                           //如果给该元素赋值为非0    
            {
                triple.e = newE;  //将表中该元素修改为另一个不为0的新值
            }

            return true;
        }

        //表中不存在此元素
        if (newE.Equals(default(E)))    //如果给该元素赋值为0
        {
            return true;                //表无变化，元素仍是零值，操作无碍，返回真。
        }

        //如果给该元素赋值为非0，往表中插入    
        Triple newTriple = new Triple  //创建新的三元组
        {
            r = i,
            c = j,
            e = newE,
        };

        int k = 0;
        while (k < Nums && tripleSeqList[k].r < i) //先找所在行i
        {
            k++;
        }
        while (k < Nums && tripleSeqList[k].r == i && tripleSeqList[k].c < j) //在第i行中再找所在列j
        {
            k++;
        }

        tripleSeqList.Add(k, newTriple); //将此三元组插入到表中
        Nums++;                       //表元素个数加一

        return true;    //操作成功，返回真。   
    }

    public TSMatrix<E> Transpose2()
    {
        TSMatrix<E> transMat = new TSMatrix<E>(Cols, Rows, Nums); //定义转置后的矩阵

        if (Nums != 0) //非零矩阵转置
        {
            for (int v = 0; v < Cols; v++) //扫描矩阵的每列
            {
                for (int k = 0; k < Nums; k++) //扫描矩阵的三元组表
                {
                    if (tripleSeqList[k].c == v) //依次找到当前列的每个三元组
                    {
                        Triple triple = new Triple //据此创建新的三元组
                        {
                            r = tripleSeqList[k].c, //行号为原来的列号
                            c = tripleSeqList[k].r, //列号为原来的行号
                            e = tripleSeqList[k].e  //值为原值
                        };

                        transMat.tripleSeqList.AddLast(triple); //添加到转置矩阵的三元组表中
                    }
                }
            }

        }

        return transMat;
    }

    public TSMatrix<E> Transpose()   //快速转置    
    {
        int[] cnum = new int[Cols]; //存储矩阵每列非0元个数
        int[] cpos = new int[Cols];  //存储矩阵每列首个非0元在转置矩阵的三元组表中的下标
        //num与cpos存在如下递推关系：
        //cpos[0]=0；
        //cpos[col]=cpos[col-1]+num[col-1]；   1 ≤ col <Cols

        TSMatrix<E> transMat = new TSMatrix<E>(Cols, Rows, Nums); //定义转置后的矩阵
        for (int i = 0; i < Nums; i++)
        {
            transMat.tripleSeqList.AddLast(new Triple());
        }

        if (Nums != 0) //非零矩阵转置
        {
            for (int k = 0; k < Nums; k++) //扫描矩阵的三元组表
            {
                cnum[tripleSeqList[k].c]++; //求矩阵每列非0元素的个数
            }

            cpos[0] = 0; //矩阵第0列首个非0元在转置矩阵的三元组表中的下标必为0
            for (int v = 1; v < Cols; v++) //从第1列起扫描矩阵的每列
            {
                cpos[v] = cpos[v - 1] + cnum[v - 1]; //求每列非0首元在转置矩阵的三元组表中的下标
            }

            int col, s;
            for (int k = 0; k < Nums; k++) //扫描矩阵的三元组表
            {
                col = tripleSeqList[k].c; //记录当前三元组所在列的列号
                s = cpos[col]; //记录当前三元组在转置矩阵的三元组表中的位置

                Triple triple = new Triple    //创建新的三元组
                {
                    r = tripleSeqList[k].c,   //行号为原来的列号
                    c = tripleSeqList[k].r,   //列号为原来的行号
                    e = tripleSeqList[k].e    //值为原值
                };

                transMat.tripleSeqList[s] = triple; //修改三元组在转置矩阵的三元组表中位置
                cpos[col]++; //预设同一列下一个三元组在转置阵中的下标
            }
        }

        return transMat;
    }

    public TSMatrix<E> Add(TSMatrix<E> other)
    {
        int maxRows = Math.Max(Rows, other.Rows);
        int maxCols = Math.Max(Cols, other.Cols);

        TSMatrix<E> res = new TSMatrix<E>(maxRows, maxCols, 0);

        int k = 0, s = 0;
        while (k < Nums && s < other.Nums)
        {
            while (k < Nums && s < other.Nums && tripleSeqList[k].r < other.tripleSeqList[s].r)
            {
                res.tripleSeqList.AddLast(tripleSeqList[k]);
                res.Nums++;
                k++;
            }

            while (k < Nums && s < other.Nums && tripleSeqList[k].r > other.tripleSeqList[s].r)
            {
                res.tripleSeqList.AddLast(other.tripleSeqList[s]);
                res.Nums++;
                s++;
            }

            while (k < Nums && s < other.Nums &&
                tripleSeqList[k].r == other.tripleSeqList[s].r &&
                tripleSeqList[k].c < other.tripleSeqList[s].c)
            {
                res.tripleSeqList.AddLast(tripleSeqList[k]);
                res.Nums++;
                k++;
            }

            while (k < Nums && s < other.Nums &&
                tripleSeqList[k].r == other.tripleSeqList[s].r &&
                tripleSeqList[k].c > other.tripleSeqList[s].c)
            {
                res.tripleSeqList.AddLast(other.tripleSeqList[s]);
                res.Nums++;
                s++;
            }

            while (k < Nums && s < other.Nums &&
                tripleSeqList[k].r == other.tripleSeqList[s].r &&
                tripleSeqList[k].c == other.tripleSeqList[s].c)
            {
                dynamic ke = tripleSeqList[k].e;
                dynamic se = other.tripleSeqList[s].e;

                res.Amend(tripleSeqList[k].r, tripleSeqList[k].c, ke + se);
                k++;
                s++;
            }
        }

        while (k < Nums)
        {
            res.tripleSeqList.AddLast(tripleSeqList[k]);
            res.Nums++;
            k++;
        }

        while (s < other.Nums)
        {
            res.tripleSeqList.AddLast(other.tripleSeqList[s]);
            res.Nums++;
            s++;
        }

        return res;
    }

    public TSMatrix<E> Sub(TSMatrix<E> other)
    {
        return Add(-other);
    }

    public static TSMatrix<E> operator +(TSMatrix<E> X, TSMatrix<E> Y)
    {
        return X.Add(Y);
    }

    public static TSMatrix<E> operator -(TSMatrix<E> X, TSMatrix<E> Y)
    {
        return X.Add(-Y);
    }

    public static TSMatrix<E> operator -(TSMatrix<E> X)
    {
        TSMatrix<E> res = new TSMatrix<E>(X.Rows, X.Cols, X.Nums);

        for (int k = 0; k < X.Nums; k++)
        {
            dynamic temE = X.tripleSeqList[k].e;

            Triple triple = new Triple
            {
                r = X.tripleSeqList[k].r,
                c = X.tripleSeqList[k].c,
                e = -temE
            };

            res.tripleSeqList.AddLast(triple);
        }

        return res;
    }

    public void Clear()
    {
        tripleSeqList = null;
        Nums = 0;
    }

    public override string ToString()
    {
        if (Nums <= 0)
        {
            return string.Empty;
        }

        StringBuilder sb = new StringBuilder();

        sb.AppendLine($"\t{Rows}\t{Cols}\t{Nums}");
        sb.AppendLine("\t-------------------");
        for (int k = 0; k < Nums; k++)
        {
            sb.AppendLine($"\t{tripleSeqList[k].r}\t{tripleSeqList[k].c}\t{tripleSeqList[k].e}");
        }

        return sb.ToString();
    }
}

class TSMatrix
{
    static void Main(string[] args)
    {
        int[,] sparseMatrix = //6*7
        {
            {0, 0, 1, 0, 0, 0, 0,},
            {0, 2, 0, 0, 0, 0, 0,},
            {3, 0, 0, 0, 0, 0, 0,},
            {0, 0, 0, 5, 0, 0, 0,},
            {0, 0, 0, 0, 6, 0, 0,},
            {0, 0, 0, 0, 0, 7, 4,},

        };

        TSMatrix<int> tSMatrixA = new TSMatrix<int>(sparseMatrix);
        Console.WriteLine(tSMatrixA);
        tSMatrixA.SparseMatrix().Print();

        //TSMatrix<int> tSMatrixB = new TSMatrix<int>("三元组/三元组.txt");
        //tSMatrixB.Assign(5, 5, out int a);
        //Console.WriteLine(a);
        //Console.WriteLine(tSMatrixB.Transpose());
        //Console.WriteLine(tSMatrixB.Transpose2());

        //TSMatrix<int> tSMatrix1 = new TSMatrix<int>("三元组/三元组2.txt");
        //TSMatrix<int> tSMatrix2 = new TSMatrix<int>("三元组/三元组3.txt");

        //TSMatrix<int> tSMatrix3 = tSMatrix1 + tSMatrix2;
        //TSMatrix<int> tSMatrix4 = tSMatrix1 - tSMatrix2;

        //Console.WriteLine(tSMatrix3);
        //Console.WriteLine(tSMatrix4);
    }
}
